import java.util.Arrays;
import java.util.Stack;

/**
 * Hoare法:
 * 最左值做key，右边先走找比key小的，找到停下来，左边开始走找比key大的，找到停下来与右边交换，直到左右相遇，再把key值与相遇点的值交换，这一趟就把key的位置确定下来了
 * key的左边都是小于ley的值，key的右边都是大于key的值；然后key作为中间值去递归左边和右边的元素，先递归左，左树，最左做Key,就这样循环，开始位置大于结束位置则结束递归
 * 时间复杂度：O(N*logN)[最好情况] O(N^2)[最坏情况，数据是有序的或者逆序的]
 * 空间复杂度：O(logN)[最好情况]  O(N)[最坏情况]
 * 稳定性：不稳定
 */

public class QuickSort {
    public static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }


    //非递归的快速排序
    public static void NorQuickSort(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int start = 0;
        int end = array.length-1;

        //小区间优化：当递归到最后20层的时候就开始直接插入排序
        if(end - start + 1 <= 20) {
            //直接插入排序
            insertSort2(array,start,end);
            return;
        }

        //三数取中
        int mid = threeNumMid(array,start,end);
        //交换mid和start
        Swap(array,mid,start);


        int pivot = partition2(array,start,end);

        if(pivot > start+1) {
            stack.push(start);
            stack.push(pivot-1);
        }

        if(pivot < end-1) {
            stack.push(pivot+1);
            stack.push(end);
        }

        while(!stack.isEmpty()) {
            end = stack.pop();
            start = stack.pop();


            //小区间优化：当递归到最后20层的时候就开始直接插入排序
            if(end - start + 1 <= 20) {
                //直接插入排序
                insertSort2(array,start,end);
                //return;//这里不能return 否则相当于只排序了一部分
            }else {
                //三数取中
                mid = threeNumMid(array,start,end);
                //交换mid和start1
                Swap(array,mid,start);

                //这是找基准做Key的时候，就是找三数取中交换后的数据
                pivot = partition2(array,start,end);

                if(pivot > start+1) {
                    stack.push(start);
                    stack.push(pivot-1);
                }

                if(pivot < end-1) {
                    stack.push(pivot+1);
                    stack.push(end);
                }
            }

        }
    }

    /**
     * 优化1：
     * 三数取中：针对有序或者逆序的情况，找到三个数的中间值，与最左交换
     * @return 返回中间数字的下标
     * 假设 L(3)<R(9) X是中间值
     * x < 3 < 9
     * 3 < x < 9
     * 3 < 9 < x
     *
     * 假设 L(9) > R(3) X是中间值
     * x > 9 > 3
     * 9 > x > 3
     * 9 > 3 > x
     */

    private static int threeNumMid(int[] array,int left,int right) {
        int mid = (left+right)/2;
        if(array[left] < array[right]) {
            if (array[mid] < array[left]) {
                return left;
            }else if(array[mid] < array[right]) {
                return mid;
            }
            else {
                return right;
            }
        } else {
            if(array[right] > array[mid]) {
                return right;
            }else if(array[left] > array[mid]) {
                return mid;
            }
            else {
                return left;
            }
        }
    }

    //直接插入排序
    public static void insertSort2(int[] array,int left,int right) {
        for(int i = left+1; i <= right;i++) {
            int tmp = array[i];
            int j = i - 1;
            for(;j >= left; j--) {
                //此处为稳定，如果加个等于就变为不稳定了
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    //array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }


    public static int count = 0;
    private static void quick(int[] array,int start,int end) {
        if(start >= end) {
            return;
        }

        count++;

        //小区间优化：当递归到最后20层的时候就开始直接插入排序
        if(end - start + 1 <= 20) {
            //直接插入排序
            insertSort2(array,start,end);
            return;
        }
         //三数取中
        int mid = threeNumMid(array,start,end);
        //交换mid和start
        Swap(array,mid,start);

        //这是找基准做Key的时候，就是找三数取中交换后的数据
        int pivot = partition1(array,start,end);

        quick(array,start,pivot-1);//左树
        quick(array,pivot+1,end);//右树
    }



    private static int partition1(int[] array,int left,int right) {
        //i记录下来原来的left
        int i = left;
        int key  = array[left];
        while(left < right) {
            //不写等于可能会发生死循环（最左和最右的值相同）
            while(left < right && array[right] >= key) {
                right--;
            }
            while(left < right && array[left] <= key) {
                left++;
            }
            //此时right指向的是小于key的值，left指向的是大于key的值，交换
            Swap(array,left,right);
        }
        //相遇点和key值交换
        Swap(array,left,i);

        //返回相遇点（left和right都可以）
        return left;
    }

    /**
     * 挖坑法：最左值做坑，最右边先走找比坑小的，找到则把右值给坑，这个右边比坑小的值成为新的坑，直到左和右相遇，相遇则把记录下来的第一个坑的值放到相遇位置
     *
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int partition2(int[] array,int left,int right) {
        int key  = array[left];
        while(left < right) {
            //不写等于可能会发生死循环（最左和最右的值相同）
            while(left < right && array[right] >= key) {
                right--;
            }
            array[left] = array[right];
            while(left < right && array[left] <= key) {
                left++;
            }
            array[right] = array[left];
        }
        //原坑值给新坑值（左右相遇点）
        array[left] = key;

        //返回相遇点（left和right都可以）
        return left;
    }


    /**
     * 前后指针法：
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int partition3(int[] array, int left, int right) {
        int prev = left ;
        int cur = left+1;
        while (cur <= right) {
            if(array[cur] < array[left] && array[++prev] != array[cur]) {
                Swap(array,cur,prev);
            }
            cur++;
        }
        Swap(array,prev,left);
        return prev;
    }


    public static void Swap(int[] array,int x,int y) {
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }


    public static void main(String[] args) {
        int[] array = {9,5,3,1,8,4,12,4,5,6,7,8,1,23,14,115,116,711,6,7,8,9,0,7655,324,129,888};
        NorQuickSort(array);
        System.out.println(Arrays.toString(array));
    }
}
